//
//  set.h
//  cobalt
//
//  Created by Nicolas Godbout on 2013-08-19.
//  Copyright (c) 2013 Nicolas Godbout. All rights reserved.
//

#ifndef __cobalt__set__
#define __cobalt__set__

#include <cstddef>

/*****
 Simple tree structure with excellent performance, based on
 
 Left-leaning Red-Black Trees, Robert Sedgewick
 http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
 
 *****/

template <class T>
class Node;

template <class T>
class Set {
    Node<T>*    root;
public:
    Set() : root(NULL) {}
    
    const T& search(T) const;
    Set& insert(T);
    Set& remove(T);
    bool traverse();
};

template <class T>
void printDot(Set<T>);


/** Implementation **/

#define RED true
#define BLACK false

struct Set_Node {
    Set_Node    *left, *right;
    bool        color;
    
    Set_Node() : left(NULL), right(NULL), color(RED) {}
    
    Set_Node* min();
    void flipColors();
};

Set_Node* rotateLeft(Set_Node*);
Set_Node* rotateRight(Set_Node*);

template <class T>
struct Node : public Set_Node {
    T           key;
    
    Node(T k) : Set_Node(), key(k) {}
    ~Node();
    
    static Node* insert(T, Node* node);
    Node* remove(T);
    Node* get(T);
};

template <class T>
Set<T>&
Set<T>::insert(T key) {
    root = Node<T>::insert(key, root);
    root->color = BLACK;
    
    return *this;
}

template <class T>
Node<T>*
Node<T>::insert(T key, Node<T>* node) {
    if ( !node )
        return new Node<T>(key);
    
    int cmp = T::compare(key, node->key);
    if (cmp == 0)
        node->key = key;
    else if (cmp < 0)
        node->left = (Node<T> *)insert(key, (Node<T> *)node->left);
    else
        node->right = (Node<T> *)insert(key, (Node<T> *)node->right);
    
    if (isRed(node->right) && notIsRed(node->left))
        node = (Node<T> *)rotateLeft(node);
    if (isRed(node->left) && node->left && isRed(node->left->left))
        node = (Node<T> *)rotateRight(node);
    if (isRed(node->left) && isRed(node->right))
        node->flipColors();
    
    return node;
}

inline bool
isRed(Set_Node *node) {
    if ( !node )
        return false;
    else
        return node->color;
}

inline bool
notIsRed(Set_Node *node) {
    if ( !node )
        return true;
    else
        return !node->color;
}

inline void
Set_Node::flipColors() {
    color = !color;
    left->color = !left->color;
    right->color = !right->color;
}


inline Set_Node*
Set_Node::min() {
    Set_Node* node = this;
    while (node->left)
        node = node->left;
    return node;
}

inline Set_Node*
rotateLeft (Set_Node* node) {
    Set_Node* x = node->right;
    node->right = x->left;
    x->left = node;
    x->color = node->color;
    node->color = RED;
    return x;
}

inline Set_Node*
rotateRight (Set_Node* node) {
    Set_Node* x = node->left;
    node->left = x->right;
    x->right = node;
    x->color = node->color;
    node->color = RED;
    return x;
}

inline Set_Node*
moveRedLeft (Set_Node* node) {
    node->flipColors();
    if (node->right && isRed(node->right->left)) {
        node->right = rotateRight(node->right);
        node = rotateLeft(node);
        node->flipColors();
    }
    return node;
}

inline Set_Node*
moveRedRight (Set_Node* node) {
    node->flipColors();
    if (node->left && isRed(node->left->left)) {
        node = rotateRight(node);
        node->flipColors();
    }
    return node;
}

inline Set_Node*
fixUp(Set_Node* node) {
    if (isRed(node->right) && notIsRed(node->left))
        node = rotateLeft(node);
    if (isRed(node->left) && node->left && isRed(node->left->left))
        node = rotateRight(node);
    if (isRed(node->left) && isRed(node->right))
        node->flipColors();
    
    return node;
}


#endif /* defined(__cobalt__tree__) */
